﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace QueuesAndStacks.CloneGraph
{
    public class Node
    {
        public int val;
        public IList<Node> neighbors;

        public Node()
        {
            val = 0;
            neighbors = new List<Node>();
        }

        public Node(int _val)
        {
            val = _val;
            neighbors = new List<Node>();
        }

        public Node(int _val, List<Node> _neighbors)
        {
            val = _val;
            neighbors = _neighbors;
        }
    }
    class MainProject
    {
        static void Main(string[] args)
        {
            Node graphNode1 = new Node(1);
            Node graphNode2 = new Node(2);
            Node graphNode3 = new Node(3);
            Node graphNode4 = new Node(4);

            graphNode1.neighbors.Add(graphNode2);
            graphNode1.neighbors.Add(graphNode4);

            graphNode2.neighbors.Add(graphNode1);
            graphNode2.neighbors.Add(graphNode3);

            graphNode3.neighbors.Add(graphNode2);
            graphNode3.neighbors.Add(graphNode4);

            graphNode4.neighbors.Add(graphNode1);
            graphNode4.neighbors.Add(graphNode3);

            //DFS(graphNode1);
            Console.ReadKey();
        }

        /// <summary>
        /// 自己写的bfs
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public static Node CloneGraph1(Node node)
        {
            if (node == null) return null;
            //GraphNode root = new GraphNode(node.val);
            if (node.neighbors.Count == 0) return new Node(node.val);
            //BFS
            Queue<Node> que = new Queue<Node>();
            HashSet<int> hash = new HashSet<int>();
            Dictionary<int,Node> dic = new Dictionary<int, Node>();
            que.Enqueue(node);
            while (que.Any())
            {
                int size = que.Count;
                for (int i = 0; i < size; i++)
                {
                    Node graphNode = que.Dequeue();
                    Node root = null ;
                    if (dic.ContainsKey(graphNode.val))
                    {
                        root = dic[graphNode.val];
                    }
                    else
                    {
                        root = new Node(node.val, new List<Node>());
                        dic.Add(node.val, root);
                    }
                    for (int j = 0; j < graphNode.neighbors.Count; j++)
                    {
                        if (dic.ContainsKey(graphNode.neighbors[j].val))
                        {
                            root.neighbors.Add(dic[graphNode.neighbors[j].val]);
                        }
                        else
                        {
                            Node graphNode1 = new Node(graphNode.neighbors[j].val, new List<Node>());
                            root.neighbors.Add(graphNode1);
                            if (hash.Add(graphNode.neighbors[j].val)) que.Enqueue(graphNode.neighbors[j]);
                            dic.Add(graphNode1.val, graphNode1);
                        }
                    }
                }
            }
            Console.WriteLine(dic[1]==node);
            return dic[node.val];

        }
    }
}
